package sort;
/**归并排序*/
import java.util.Arrays;

public class MergeSort {
    public static void main(String[] args) {
        int [] arr = {8,6,1,7,5,3,2,9,4,0};
        arr=sortArray(arr ,0, arr.length-1);
        System.out.println(Arrays.toString(arr));
    }

    private static int [] sortArray(int[] arr ,int left ,int right) {
        if(left==right){
            return arr= new int[]{arr[left]};
        }
        int mid=left+(right-left)/2;
        int [] leftArray = sortArray(arr,left,mid);
        int [] rightArray = sortArray(arr,mid+1,right);
        int [] newArray = new int[leftArray.length+rightArray.length];
        int l=0,r=0,n=0;
        while (l<leftArray.length && r<rightArray.length){
            newArray[n++] = leftArray[l]<=rightArray[r] ? leftArray[l++] : rightArray[r++];
        }
        while(l<leftArray.length){
            newArray[n++]=leftArray[l++];
        }
        while (r<rightArray.length){
            newArray[n++]=rightArray[r++];
        }
        return newArray;
    }
}
